import numpy as np


def right_index(url1, url2):
    a = np.array(found_error_index(url1, url2)[1])
    # 对于index1,索引为-1表示在字符串前面插入一位，类型：1表示当前索引修改一位，2表示当前索引删除一位，3表示当前索引的后面插入一位
    # 对于index2,索引为-1表示在字符串前面插入一位，类型：1表示当前索引修改一位，2表示当前索引的后面插入一位，3表示当前索引删除一位
    b = a[:, 4] > 0
    b = a[b] - 1
    x = np.concatenate((b[:, 2].reshape([-1, 1]), (b[:, 4] + 1).reshape([-1, 1])), axis=1)
    y = np.concatenate((b[:, 3].reshape([-1, 1]), (b[:, 4] + 1).reshape([-1, 1])), axis=1)
    error_index1 = x[x[:, 0].argsort()]
    error_index2 = y[y[:, 0].argsort()]
    index_1 = [i for i in range(len(url1))]
    index_2 = [i for i in range(len(url2))]
    for i in error_index1:
        if i[1] != 3:
            if i[0] in index_1:
                index_1.remove(i[0])
    for i in error_index2:
        if i[1] != 2:
            if i[0] in index_2:
                index_2.remove(i[0])

    return index_1, index_2  # 返回正确文字的索引


def found_error_index(result1, result2):
    matrix = [[i + j for j in range(len(result2) + 1)] for i in range(len(result1) + 1)]

    choose = [[[max(0, i - 1), max(0, j - 1), max(0, i), max(0, j), 1] for j in range(len(result2) + 1)] for i in
              range(len(result1) + 1)]
    choose[0][0] = [-1, -1, 0, 0, 0]
    for i in range(1, len(result1)):
        choose[i][0][-1] = 2
    for j in range(1, len(result2)):
        choose[0][j][-1] = 3
    for i in range(1, len(result1) + 1):
        for j in range(1, len(result2) + 1):
            d = int(result1[i - 1] != result2[j - 1])
            if matrix[i - 1][j] + 1 < matrix[i][j - 1] + 1:
                if matrix[i - 1][j] + 1 > matrix[i - 1][j - 1] + d:
                    matrix[i][j] = matrix[i - 1][j - 1] + d
                    choose[i][j] = [i - 1, j - 1, i, j, d]
                else:
                    matrix[i][j] = matrix[i - 1][j] + 1
                    choose[i][j] = [i - 1, j, i, j, 2]
            else:
                if matrix[i][j - 1] + 1 > matrix[i - 1][j - 1] + d:
                    matrix[i][j] = matrix[i - 1][j - 1] + d
                    choose[i][j] = [i - 1, j - 1, i, j, d]
                else:
                    matrix[i][j] = matrix[i][j - 1] + 1
                    choose[i][j] = [i, j - 1, i, j, 3]
    path = recursion_path(choose, [len(result1), len(result2)])
    path = path[:-1]
    return matrix[len(result1)][len(result2)], path


def recursion_path(choose, location):
    path = []
    if location != [-1, -1]:
        path.append(choose[location[0]][location[1]])
        path.extend(recursion_path(choose, choose[location[0]][location[1]][:2]))
    return path